package offer.offer03;

import java.util.LinkedList;
import java.util.List;

/**
 * 100, 68 递归还是什么, 把当前深度传下去, 然后把最大深度传上来;
 */
public class Solution55 {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return findDepth(root, 0);
    }

    public int findDepth(TreeNode node, int fathLen){
        int curDepth = fathLen + 1;
        int leftLen = node.left == null? curDepth : findDepth(node.left, curDepth);
        int rightLen = node.right == null? curDepth : findDepth(node.right, curDepth);
        return Math.max(curDepth, Math.max(leftLen, rightLen));
    }

    //服了服了
    public int maxDepth2(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    //这里用两个List, 这个层序遍历BFS就很直观
    public int maxDepth3(TreeNode root) {
        if(root == null) return 0;
        List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
        int res = 0;
        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);
        System.out.println(new Solution55().maxDepth(root));
    }
}
